package Point.Double;

import org.junit.Test;

import java.util.*;


/**
 * [文档]
 *      // -1 -1 0 2 -> 1.去fir重 / 2.重的从第一个开始
 *      // fir : -1 -1 0 2 -> 1.去fir重 / 2.重的从第一个开始
 *
 * 【总结】
 *      0 * sum3 易错点
 *          a) i=0不是1 起 -> [1,1,1]
 *          b) 特: -1 -1 0 1 -> 2个 [-1 0 1]
 *              -> 对 fir 去重 ：
 *                      要从 第一个 -1 开始计算
 *                      因为 -1 -1 0 2 -> -1 -1 2 不能丢
 *              -> 解决：[看草稿！]
 *                   if(nums[fir] == FIR) continue;
 *              （ 注：初 FIR = nums[0]-1 ）
 *
 *      1 while框架
 *           w(l<n && 反)
 *
 *      2 sum3 不用 w反 -> 因为 r r+1 太难处理 r=n 越界
 *          -> 改用 上轮旧值 L R
 *
 *      3 for 比旧值 板子：
 *          int FIR = nums[fir]
 *          if/w nums[fir] == FIR
 *
 */
/**
 * 新 7.17
 *
 * nsum 递归嵌套 思路：
 *      因为 res 是 最顶层 f(n) 1个的
 *      中间  fn-1 要 fn-2 要 fn-3 .. 要 f2 r
 *      最后 我只要 最顶层 的 f(n) 的 return
 */
/**
 *  debug:
 *   -4 -1 -1  0 1 2
 *   0  1  2   3 4 5
 */
public class 三数之和15 {
    // [1 好] while去重 -> (不用Set用While - 虽 易错点多 但 有理可依！)
    public List<List<Integer>> threeSum(int[] nums) {

        // 忘sort （本题要val 可以sort）
        Arrays.sort(nums);

        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;

        int FIR = nums[0]-1 ; // 看草稿
        for (int i = 0; i <= n-3; i++) { //特：[0,0,0] -> i=1 改成 0
            // 特: -1 -1 0 1 -> 2个 [-1 0 1]
            // -> 干想 纯浪费时间
            // * -> 草稿 2分钟 解决
            int fir = i, l = i+1, r = n-1;
            if(nums[fir] == FIR){
                continue;
            }
            FIR = nums[fir];

            while (l < r) { // 少了 内w
                int L = nums[l], R = nums[r];
                int sum3 = FIR + L + R; // 少写成 L+R

                // 找到
                if (sum3 == 0) {
                    res.add(Arrays.asList(new Integer[]{FIR, L, R}));
                    // 左右 *都* 到不同
                    while (l < n && nums[l] == L) {
                        l++;
                    }// -> 反：nums[l] != l [不用 i-1!=i 因为 r r+1 要处理 r=n 太麻烦]
                    while (r >= i && nums[r] == R) {
                        r--;
                    }// * [先想结果 反上去条件] 3444 应该出时 r != r+1
                }
                // 没找到 -> 左右 *分别* 到不同
                else if (sum3 < 0) {
                    while (l < n && nums[l] == L) { // 同上
                        l++;
                    }
                } else if (sum3 > 0) {
                    while (r >= i && nums[r] == R) { // 同上
                        r--;
                    }
                }
            }

        }
        return res;
    }

    // [2 不推荐] set这个太虚 没底 -> 改用 while去重
    public List<List<Integer>> threeSum_set(int[] nums) {
        Set<List<Integer>> res = new HashSet<>();
        // 先写 中文 注释架
        // 排序
        Arrays.sort(nums);
        // i<n-2
        for (int i = 0; i < nums.length - 2; i++) {
            System.out.println("-"+i);
            // i+1 n-1 双指针 ，找到 tmp{i,l,r}
            findCombineByIThenPutInRes(i+1, nums, res);
        }
        return new ArrayList<>(res);
    }
    /**
     *
     * 【蒙了试下】
     * -1 0 0 2 3
     *
     * -1 - 0 3
     * -1 - 0 2
     * -1 - 0 0
     *
     * -> 不同于mid的二分，这个必须是2个元素，所以l=r不能进入w处理
     */
    void findCombineByIThenPutInRes(int i,int[] nums, Set<List<Integer>> res){
        int left = i, right = nums.length - 1;
        while(left < right){
            int curSum = nums[i] + nums[left] + nums[right];
            if(curSum == 0){
                List<Integer> tmp = new ArrayList<>();
                Collections.addAll(tmp, nums[i], nums[left], nums[right]);
                res.add(tmp);
                // 切记不break，可能多种组合
                left++; right--; // 迭代
            } else if(curSum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }

    @Test
    public void test(){
//        int[] nums = new int[]{-1,0,1,2,-1,-4};
        int[] nums = new int[]{0,0,0}; // 308/318
        System.out.println("RES:" + threeSum(nums));
    }
}
